package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

/**
 * Created by iFish on 2017/7/10.
 */

//Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
//
//        Note: You may not slant the container and n is at least 2.

public class _0011 extends BaseLeetCodeProblem {
    @Override
    public String title() {
        return "Container With Most Water";
    }

    @Override
    public void run() {
        super.run();

        int len = 15000;
        int []height = new int[len];
        for (int i = len - 1; i >= 0; i--) {
            height[len - 1 - i] = i;
        }
//        for (int i = 0; i < len - 1; i++) {
//            height[i] = i;
//        }
        int r = maxArea(height);
        printResult(r);
    }

    public int maxArea(int[] height) {
        int r = 0;
        int b = 0, e = height.length - 1;
        while (b < e) {
            int hb = height[b], he = height[e];
            boolean bigger = he > hb;
            r = Math.max((bigger ? hb : he) * (e - b), r);
            if (bigger) {
                b++;
            } else {
                e--;
            }
        }
        return r;
    }
}
